package com.cat.math;

import java.util.ArrayList;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-count-of-numbers-which-are-not-special/description/
 * @create 2025/10/16 15:31
 * @since JDK17
 */

public class Solution09 {
    static int N = ((int) (1e5 + 10));
    static boolean[] isPrime = new boolean[N];
    static ArrayList<Integer> list = new ArrayList<>();
    static {
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i < N; i++) {
            if (!isPrime[i]) {
                list.add(i);
                for (long j = (long) i * i; j < N; j += i) {
                    isPrime[(int) j] = true;
                }
            }
        }

    }
    public int nonSpecialCount(int l, int r) {
        int ans = r - l + 1;
        for (long num : list) {
            if (num * num > r) {
                break;
            }
            if (num * num >= l) {
                ans--;
            }
        }

        return ans;
    }
}
